class Solution {
public:
    int firstMissingPositive(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (n == 0) {
            return 1;
        }

        for (int i = 0; i < n; ++i) {
            int pos = A[i];
            while (pos > 0 && pos <= n && A[pos - 1] != pos) {
                int t = A[pos - 1];
                A[pos - 1] = pos;
                pos = t;
            }
        }
        int ans = 1;
        for (; ans <= n && A[ans - 1] == ans; ++ans) {
        }

        return ans;
    }
};
